1564. Теория чисел

Для заданного натурального числа n найдите количество таких чисел m, что 1 ≤ m ≤ n, НОД(m, n) ≠ 1 и НОД(m, n) ≠ m. Через НОД здесь обозначен “Наибольший Общий Делитель”.

Вход. Каждая строка содержит одно натуральное число n (0 < n < 2³¹).

Выход. Для каждого значения n вывести в отдельной строке количество искомых чисел m.

Пример входа	Пример выхода
1 2 6 2147000000	0 0 1 1340599805

РЕШЕНИЕ

теория чисел – функция Эйлера

Анализ алгоритма

Из числа n следует вычесть количество взаимно простых с ним чисел, равное функции Эйлера j(n) (если m и n взаимно просты, то НОД(m, n) = 1), и количество его делителей (если m является делителем n, то НОД(m, n) = m). При этом число 1 будет одновременно и взаимно простым с n и делителем n. Поэтому к полученной разности следует прибавить 1.

Если n = – разложение числа n на простые множители, то оно имеет d(n) = (k₁ + 1) * (k₂ + 1) * … * (k_t + 1) делителей.

Таким образом, количество искомых значений m для заданного n равно

n – j(n) – d(n) + 1

Пример

Пусть n = 10. Имеем j(10) = 4 числа, взаимно простых с 10: 1, 3, 7, 9.

Число 10 имеет d(10) = d(2 * 5) = 2 * 2 = 4 делителей: 1, 2, 5, 10.

Количество чисел m, таких что 1 ≤ m ≤ 10, НОД(m, 10) ≠ 1 и НОД(m, 10) ≠ m, равно

10 – j(10) – d(10) + 1 = 10 – 4 – 4 + 1 = 3

Реализация алгоритма

Функция euler вычисляет функцию Эйлера. Одновременно в переменной common подсчитываем количество делителей числа n по выше приведенной формуле. В цикле for при встрече делителя i числа n, в переменной div вычисляем степень, с которой i входит в число n. То есть div является максимальной степенью, для которой n делится на i^div.

int euler(int n)

{

int i, result = n, div;

common = 1;

for(i = 2; i <= sqrt(n); i++)

if (n % i == 0)

{

div = 0;

result -= result / i;

while (n % i == 0) {n /= i; div++;}

common *= div + 1;

}

if (n > 1) {result -= result / n; common *= 2;}

return result;

}

Основной цикл программы. Для каждого входного значения n вычисляем результат n – j(n) – common + 1, где common = (k₁ + 1) * (k₂ + 1) * … * (k_t + 1), и выводим его.

while(scanf("%d",&n) == 1)

{

res = n - euler(n) - common + 1;

printf("%d\n",res);

}